package oct2013.linkednode;

import java.util.LinkedList;
import java.util.Queue;

public class PopulatingNextRightPointersinEachNode {
	public void connect(TreeLinkNode root) {
		if (root == null)
			return;
		Queue<Object[]> q = new LinkedList<Object[]>();
		TreeLinkNode cur = root;
		TreeLinkNode prev = null;
		int ph = -1;
		Integer height = new Integer(0);
		Object[] node = new Object[2];
		node[0] = cur;
		node[1] = height;
		q.add(node);
		while (!q.isEmpty()) {
			Object[] pair = q.poll();
			cur = (TreeLinkNode) pair[0];
			height = (Integer) pair[1];
			if (ph == height.intValue()) {
				prev.next = cur;
			}
			ph = height.intValue();
			prev = cur;
			if (cur.left != null) {
				node = new Object[2];
				node[0] = cur.left;
				node[1] = new Integer(height.intValue() + 1);
				q.add(node);
			}
			if (cur.right != null) {
				node = new Object[2];
				node[0] = cur.right;
				node[1] = new Integer(height.intValue() + 1);
				q.add(node);
			}
		}
	}
}
